package com.tyrone.algorithm.priority;

/**
 * 最大优先队列
 * @param <T>
 */
public class MaxPriorityQueue <T extends Comparable>{
    private T[] items ;  //用来存储元素的数组
    private int N;       //记录堆中元素的个数

    public MaxPriorityQueue(int capacity){
        items= (T[]) new Comparable[capacity+1];
        N=0;
    }
    /**
     * 判断堆中索引i处的元素是否小于索引j处的元素
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i,int j){
        return items[i].compareTo(items[j])<0;
    }

    /**
     * 交换堆中i索引和j索引处的值
     * @param i
     * @param j
     */
    private void exch(int i,int j){
        T item = items[i];
        items[i]=items[j];
        items[j]=item;
    }

    /**
     * 删除队列中最大的元素,并返回这个最大元素
     * @return
     */
    public T delMax(){
        T maxItems = items[1];
        exch(1,N);
        items[N]=null;
        N--;
        sink(1);
        return maxItems;
    }

    /**
     * 往队列中插入一个元素
     * @param t
     */
    public void insert(T t){
        items[++N]=t;
        swim(N);
    }

    /**
     * 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
     * @param k
     */
    private void swim(int k){
        while (k>1){
            if (less(k,k/2)){
                return;
            }else {
                exch(k,k/2);
            }
            k/=2;
        }
    }

    /**
     * 使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
     * @param k
     */
    private void sink(int k){
        while (2*k<=N){
            int max =2*k;;
            if (2*k+1<=N) {
                if (less(2 * k, 2 * k + 1))
                    max = 2 * k + 1;
            }
            if (less(k,max)){
                exch(k,max);
            }else {
                break;
            }
            k=max;
        }
    }

    /**
     * 获取队列中元素的个数
     * @return
     */
    public int size(){
        return N;
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty(){
        return N==0;
    }

}
